Technical Field
The present invention relates to hash table structures, particularly to multi-level hash tables (MHTs) and nested multi-level hash tables (NMHTs), and to hash table configurations in field programmable gate arrays.
Description of the Related Art
MHTs provide a high space efficiency approach to storing keys in a hash table. In a MHT, a hash table is divided into multiple blocks by using different hash functions. This approach improve the space efficiency of key storage.
A Field Programmable Gate Array (FPGA) is a semiconductor device that is programmable in the field after manufacturing. A FPGA has a large number of logic gates in an array and have exhibit parallel computation abilities.
FPGA chips have small memory blocks that can hold only a relatively small number of data entries per block. In each clock cycle, FPGA logic circuits can read or write only one data entry stored in one memory address of a memory block. Thus, the throughput of a hash table built in FPGA memory blocks could be limited by the clock frequency of the FPGA.